package com.lw.leetcode.hash.b;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 1235. 规划兼职工作
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/8 15:45
 */
public class JobScheduling {

    public static void main(String[] args) {
        JobScheduling test = new JobScheduling();


        // 120
//        int[] a = {1, 2, 3, 3};
//        int[] b = {3, 4, 5, 6};
//        int[] c = {50, 10, 40, 70};

        // 150
//        int[] a = {1,2,3,4,6};
//        int[] b = {3,5,10,6,9};
//        int[] c = {20,20,100,70,60};

        // 6
//        int[] a = {1,1,1};
//        int[] b = {2,3,4};
//        int[] c = {5,6,4};

        // 18
//        int[] a = {4, 2, 4, 8, 2};
//        int[] b = {5, 5, 5, 10, 8};
//        int[] c = {1, 2, 8, 10, 4};

        // 41
        int[] a = {6,15,7,11,1,3,16,2};
        int[] b = {19,18,19,16,10,8,19,8};
        int[] c = {2,9,1,19,5,7,3,19};

        int i = test.jobScheduling(a, b, c);
        System.out.println(i);
    }




    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int length = startTime.length;
        int[][] arr = new int[length][3];
        for (int i = length - 1; i >= 0; i--) {
            int[] ints = arr[i];
            ints[0] = startTime[i];
            ints[1] = endTime[i];
            ints[2] = profit[i];
        }
        Arrays.sort(arr, (a, b) -> Integer.compare(a[1], b[1]));
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(0, 0);
        int max = 0;
        for (int i = 0; i < length; i++) {
            int[] ints = arr[i];
            Integer key = map.floorKey(ints[0]);
            int m = Math.max(map.getOrDefault(ints[1], 0), map.get(key) + ints[2]);
            max = Math.max(max, m);
            map.put(ints[1], max);
        }
        return max;
    }

}
